package com.qf.arith;

import java.util.HashSet;
import java.util.Set;

/**
 * 链表是否有环
 *
 * @author lixu
 */
public class TestIsCycle {


    //链表  单向
    static class Node<T> {
        T value;//值
        Node<T> next;//后继

        public Node(T value) {
            this.value = value;
        }
    }

    public static void main(String[] args) {
        Node<Integer> node1 = new Node<>(3);
        Node<Integer> node2 = new Node<>(8);
        Node<Integer> node3 = new Node<>(1);
        Node<Integer> node4 = new Node<>(9);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        //有环
        //node4.next = node2;
        //头节点
   /*     Node<Integer> p = node1;//临时变量
        while (p!=null){
            System.out.print(p.value + " ");
            p = p.next;
        }*/

        //是否有环
        System.out.println("是否有环：" + isCycle2(node1));

    }

    /**
     *  是否有环  Set集合
     * @param node1   空间复杂度O(n)   时间复杂度O(3n+2)  O(n)
     * @return
     */
    private static boolean isCycle2(Node<Integer> node1) {
        Set<Node> nodeSet = new HashSet<>();//1     n
        Node<Integer> p = node1;//1
        while (p!=null){ // n     3n+2=
            if(nodeSet.contains(p)){//1
                //有环
                return true;
            }
            //保存
            nodeSet.add(p);//1
            //下一个链表
            p=p.next;//1
        }
        //没有环
        return false;

    }


    /**
     * 算法： 判断上面的链表是否有环  链表的长度是n
     * O(n)  == 发现我昨天写的这个算法  一般算法   O(1)
     */
    private static boolean isCycle(Node<Integer> node1) {
        //快指针
        Node<Integer> fast = node1;//1行
        //慢指针
        Node<Integer> slow = node1;//1行
        //如存在环，则两者相遇；如不存在环，fast遇到NULL退出

        //fast!=null 节点是偶数的时候
        //fast.next!=null : 节点是奇数的时候
        while (fast!=null && fast.next!=null) {//  n/2*4=2n+2 = n
            fast=fast.next.next;//走二步 //1行
            slow=slow.next;//走一步  //1行
            if(fast == slow){  //1行
                return true;  //1行
            }
        }
        //没有环     n/2*3+1= 3n/2+1  =  n
        return false;
    }

}
